/**
 * 输入一个链表，输出该链表中倒数第k个节点
 * 
 * 示例：
 * 给定一个链表: 1->2->3->4->5, 和 k = 2
 * 返回链表 4->5
 * 
 */


#include "common.h"


 /* 
 * 解决思路：
 * 快慢指针，先让快指针走k步，然后两个指针同步走，当快指针走到头时，慢指针就是链表倒数第k个节点。
 */

struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    struct ListNode* first = head;
    struct ListNode* second = head;
    int i = k;
    for(i=k; i>0; i--){
        first = first->next;
        // 此处的判断是否有必要验证链表的长度不小于 K
        if(!first && i>1){
            return NULL;
        }
    }
    while(first){
        first = first->next;
        second = second->next;
    }
    return second;
}